#include<bits/stdc++.h>
using namespace std;
const int N=100004;

int n,m;
short price[N];
vector<int> edges[N];
//
short res=0;
int values[N][3];

struct Node{
    int pos;
    int buy,sell;
    int state;
    Node(){
        buy=sell=0;
    }
    Node(int pos,int buy,int sell,int state){
        this->pos=pos;
        this->buy=buy;
        this->sell=sell;
        this->state=state;
    }
    int getv(){
        if(state==0||state==1) return 0;
        return sell-buy;
    }
    bool operator<(const Node& node) const{
        int v1,v2;
        if(state==0||state==1) v1=0;
        else v1=sell-buy;
        //v2
        if(node.state==0||node.state==1) v2=0;
        else v2=node.sell-node.buy;
        return v1>v2;
    }
};

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        cin>>price[i];
    }
    for(int i=1;i<=m;i++){
        int s,t,ty;
        cin>>s>>t>>ty;
        if(ty==1){
            edges[s].emplace_back(t);
        }else{
            edges[s].emplace_back(t);
            edges[t].emplace_back(s);
        }
    }
    res=0;
    priority_queue<Node> que;
    memset(values,0xff,sizeof(values));
    que.push(Node(1,0,0,0));
    values[1][0]=0;
    while (!que.empty())
	{
        Node node=que.top();
        que.pop();
        int pos=node.pos;
        int state=node.state;
        if(node.getv()<values[pos][state]) continue;
        cout<<"node:"<<pos<<" "<<state<<" "<<node.getv()<<endl;
        for(auto t:edges[pos]){
            Node noden;
            noden.pos=t;
            if(state==0){
                noden.buy=price[pos];
                noden.state=1;
                if(noden.getv()>values[t][1]){
                    que.push(noden);
                    values[t][1]=noden.getv();
                }
            }
            else if(state==1){
                noden.buy=node.buy;
                noden.sell=price[pos];
                noden.state=2;
                if(noden.getv()>values[t][2]){
                    que.push(noden);
                    values[t][2]=noden.getv();
                }
            }
            //run
            noden.buy=node.buy;
            noden.sell=node.sell;
            noden.state=node.state;
            if(noden.getv()>values[t][noden.state]){
                que.push(noden);
                values[t][noden.state]=noden.getv();
            }
        }
    }
    int res=0;
    cout<<max(0,values[n][2]);
    return 0;
}
